from typing import List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        """
        初始化一个新的树节点

        :param val: 节点的值，默认为 0
        :param left: 左节点的值，默认为 None
        :param right: 右节点的值，默认为 None
        """

        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        """
        返回一个容易阅读的字符串表示形式，用于调试
        """

        return f"TreeNode(val={self.val}, left={self.left}, right={self.right})"

    # TODO: 有待完成
    @staticmethod
    def from_list(lst):
        """
        从列表构建二叉树，列表中的元素依次表示前序遍历的结果，使用 None 表示空节点
        :param list: 前序遍历序列化的列表
        :return: 构建好的二叉树的根节点
        """

class TreeServices:
    def __init__(self, root=None):
        self.root = root

    @staticmethod
    def preorderTraversal(root: TreeNode) -> list[int]: # python 3.9+
        # -> List[int] python 3.5-3.8
        res = []
        def dfs(node):
            if node is None:
                return

            res.append(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return res

    @staticmethod
    def inorderTraversal(root: TreeNode) -> list[int]:
        res = []
        def dfs(node):
            if node is None:
                return

            dfs(node.left)
            res.append(node.val)
            dfs(node.right)
        dfs(root)
        return res

    @staticmethod
    def postorderTraversal(root: TreeNode) -> list[int]:
        res = []
        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            dfs(node.right)
            res.append(node.val)

        dfs(root)
        return res

